#!/usr/bin/env ruby

#Philip C. Pilosi   and     Todd R. Silvia 
#   668828058                  660667901

# File: BFSSearch.rb
# Usage: This file is passed a 20x20 board and searches for the goals
# 		 via breath first search.

############################## METHODS ##############################
#====================================================================

########################################
# Prints the board array as a 20x20 grid
def printBoard(board)

	for i in 0..483
		print board[i]+ " ";
		#If 22nd element make a new line
		if(((i+1) % 22) == 0)
			puts
		end
	end
end
#End printBoard()

########################################
# Searches the maze via breadth first
# search, then calls findPaths() to 
# print the paths to the goals as a result
# of the search
def preformBFS(bfsArray)
	myQueue = []	    #Queue to preform search
	listQueue = []		#Queue of all board spaces traversed
	originsArr = []		#Array of origin of how each space was traversed
	nodesVisited = []	#Holds all nodes that have been visited
	goalLocations = []	#Array locations of listQueue[] of all goals
	
	#Initalize queues
	myQueue.push(23)
	originsArr.push(-1)
	nodesVisited.push(23)
	
	#Loop to run breadth first search until queue is empty
	while myQueue.length > 0
		currNode = myQueue.shift
		listQueue.push currNode
		
		#If current spot on board is a goal then save this location
		#for further processing of a path
		if(bfsArray[currNode] == "G")
			goalLocations.push (listQueue.length - 1)
		end
		
		#Loop to check each direction (Left, Up, Right, Down) from current
		#location being checked on the board.
		for i in 0..3
			direction = DIRECTIONS[i]
			if(bfsArray[currNode+direction] != "#") #Check if location is not a wall
				#Checkes if adjacent node has been visited
				isMarked = nodesVisited.include?(currNode+direction)
				if(isMarked == false)
					#Node is not a wall and has not been visited
					nodesVisited.push(currNode+direction)
					myQueue.push(currNode+direction)
					originsArr.push(currNode)
				end
			end
		end
	end
	
	#The breadth first search is complete, this method will evaluate the paths to the goals found
	findPaths(listQueue, originsArr, goalLocations,bfsArray)
end

########################################
# Is given the data from a breadth first
# search and displays all of the paths
# from start to all goals in the maze
# assuming that they were reachable.
def findPaths(myQueue, myOrigin, myGoals, bfsBoard)
	theGoalPath = []	#List of path to current goal being checked
	
	puts "--------------------------"
	puts "BFS Search Maze Result"
	puts "--------------------------"
	puts "Number of goals found: " + (myGoals.length).to_s
	puts "Number of goals unreachable: " + (5-myGoals.length).to_s
	
	myGoals.each do |thisGoal|
		theGoalPath.push myQueue[thisGoal]
		toFind = myQueue[thisGoal]		
		
		while true
			theIndex = myQueue.find_index(toFind)
			theOrigin = myOrigin[theIndex]
			if(theOrigin == -1)
				break
			end
			theGoalPath.push theOrigin
			toFind = theOrigin
		end
		
		#print "PATH TO A GOAL: "
		#Replace board spaces with arrows to show paths
		theGoalPath.reverse!
		tempBoard = Array.new(bfsBoard)
		for k in 2...theGoalPath.length
			dirMoved = theGoalPath.at(k)-theGoalPath.at(k-1)
			if dirMoved == -1 && tempBoard[theGoalPath[k-1]] != "G"
				tempBoard[theGoalPath[k-1]] = "<"
			elsif dirMoved == -22 && tempBoard[theGoalPath[k-1]] != "G"
				tempBoard[theGoalPath[k-1]] = "^"
			elsif dirMoved == 1 && tempBoard[theGoalPath[k-1]] != "G"
				tempBoard[theGoalPath[k-1]] = ">"
			elsif dirMoved == 22 && tempBoard[theGoalPath[k-1]] != "G"
				tempBoard[theGoalPath[k-1]] = "V"
			end
		end
		
		puts "---------------------------------------------------"
		printBoard(tempBoard)
		#theGoalPath.each do |part|
		#	print part.to_s + "->"
		#end
		#puts
		theGoalPath.clear
	end
end

############################### MAIN ################################
#====================================================================

#Global Variables
DIRECTIONS = [-1,-22,1,22]; #Left,Up,Right,Down
myString = ARGV[0]			#The board input as a string from main script
bfsArray = []				#Array to hold the board

#START CODE#

#Loop to break the string of input into an array for board
for i in 0..483
	bfsArray[i] = myString[i]
end

preformBFS(bfsArray) #Preform the BFS Search and find the 
puts "--------------------------"
puts "--END BFS SEARCH RESULTS--"
puts "--------------------------"
#printBoard(bfsArray) #Pring the board with arrows showing BFS search

#END OF FILE#
